/FONT#0=BASL30/FONT#1=BASI30/FONT#2=NGR40/FONT#3=BASB30/FONT#4=SUB
␈↓␈↓↓␈↓α␈↓β␈↓∧␈↓α␈↓ β
STANFORD ARTIFICIAL INTELLIGENCE LABORATORY
␈↓ ↓H
␈↓ ∧αDEPARTMENT OF COMPUTER SCIENCE
␈↓ ↓H
␈↓ ¬	STANFORD UNIVERSITY
␈↓ ↓H
␈↓ ∧;STANFORD, CALIFORNIA 94305
␈↓ ↓H
␈↓
␈↓ ↓H

␈↓ ↓H

␈↓ ↓H

␈↓ ↓H

␈↓ ↓H

␈↓ ↓H
␈↓ α_␈↓ αh␈↓ β8␈↓ ∧λ␈↓ ∧X␈↓ ¬(
␈↓ ↓H

␈↓ ↓H
␈↓ α_␈↓ αh␈↓ β8␈↓ ∧λ␈↓ ∧X␈↓ ¬(␈↓ ¬xAugust 23, 1974
␈↓ ↓H

␈↓ ↓H

␈↓ ↓H

␈↓ ↓H
Editor
␈↓ ↓H
␈↓↓Communications of the ACM␈↓
␈↓ ↓H
ACM Headquarters Office
␈↓ ↓H
1133 Avenue of the Americas
␈↓ ↓H
New York, New York 10036
␈↓ ↓H

␈↓ ↓H
Dear Sir:
␈↓ ↓H

␈↓ ↓H
␈↓ α_Friedman␈α∀and␈α∀Hoffman␈α∀use␈α∀an␈α∀encipherment␈α∀technique␈α∀in␈α∀their␈α∪paper␈α∪␈↓↓Execution␈α∪Time
␈↓ ↓H
␈↓ ↓HRequirements␈α⊃for␈α⊃Encipherment␈α⊃Programs␈↓␈α⊂[␈↓↓Communications␈α⊂of␈α⊂the␈α⊂ACM␈↓␈α⊂17,8␈α⊂(August␈α⊂1974)]␈α⊂that
␈↓ ↓H
␈↓ ↓Hseems␈α
grossly␈αdefective.␈αWhile␈αthey␈αdon't␈αadvertise␈αit␈αas␈αgood,␈αsomeone␈αmight␈αuse␈αit␈αwith␈αregretable
␈↓ ↓H
␈↓ ↓Hresults.␈αThe␈αobject␈αof␈αthis␈αnote␈αis␈αnot␈αjust␈αto␈α
point␈α
out␈α
the␈α
defect,␈α
but␈α
to␈α
pose␈α
the␈α
problem␈α
in␈α
general,
␈↓ ↓H
␈↓ ↓Hto␈α∂make␈α∞explicit␈α∞an␈α∞␈↓βstrong␈α∞adequacy␈↓␈α∞criterion␈α∞for␈α∞ciphers,␈α∞and␈α∞to␈α∞suggest␈α∞a␈α∞modification␈α∞of␈α∞their
␈↓ ↓H
␈↓ ↓Hsystem␈α
that␈α
apparently␈α
meets␈α
it.
␈↓ ↓H

␈↓ ↓H
␈↓ α_The␈α
method␈α
they␈α
use␈α
involves␈α
the␈α
generation␈α
of␈α
a␈α
pseudo␈α
random␈αkey␈αas␈αa␈αsequence␈α{␈↓↓x␈↓∧n␈↓}␈αof
␈↓ ↓H
␈↓ ↓Hnumbers␈α⊃continued␈α⊃by␈α⊃the␈α⊃rule␈α⊃␈↓↓x␈↓∧n+1␈↓↓␈α⊃=␈α⊃ax␈↓∧n␈↓↓␈α⊃+␈α⊃c␈α⊃(mod␈α⊃p)␈α⊃␈↓where␈α⊃␈↓↓p␈↓␈α⊃is␈α⊃a␈α⊃prime.␈α⊂The␈α⊂␈↓↓x␈↓'s␈α⊂are␈α⊂then
␈↓ ↓H
␈↓ ↓H␈↓↓exclusive-or␈↓ed␈α∞with␈α∞packed␈α∞words␈α∞of␈α∞the␈α∞text␈α∞to␈α∞form␈α∞the␈α∞cryptogram.␈α∞In␈α∞the␈α∞case␈α∞in␈α∞question,␈α
the
␈↓ ↓H
␈↓ ↓Hwords␈α
are␈α
60␈α
bits␈α
long␈α
as␈α
fits␈α
the␈α
CDC␈α
6400.␈α
The␈α
cipher␈α
is␈α
attacked␈α
as␈α
follows:
␈↓ ↓H

␈↓ ↓H
␈↓ α_The␈αvillain␈αguesses␈αa␈αplain␈αtext␈αsequence␈α240␈αbits␈αlong.␈αThis␈αmay␈αnot␈αalways␈αbe␈αpossible,␈αand
␈↓ ↓H
␈↓ ↓Hhow␈α∂he␈α∂goes␈α∂about␈α∂it␈α∞depends␈α∞on␈α∞what␈α∞he␈α∞already␈α∞knows.␈α∞For␈α∞example,␈α∞he␈α∞may␈α∞know␈α∞a␈α∞favorite
␈↓ ↓H
␈↓ ↓Hphrase,␈α⊂he␈α⊂may␈α⊂suspect␈α⊂a␈α⊂quotation,␈α⊂or␈α⊂the␈α∂document␈α∂may␈α∂be␈α∂a␈α∂computer␈α∂program␈α∂containing␈α∂a
␈↓ ↓H
␈↓ ↓Hguessed␈α
subroutine␈α
or␈α
the␈α
user␈α
may␈α
be␈α
trying␈α
to␈α
keep␈α
secret␈α
a␈α
modified␈α
version␈α
of␈α
a␈α
known␈α
program.
␈↓ ↓H

␈↓ ↓H
␈↓ α_The␈αvillain␈αhas␈αa␈αcomputer␈αprogram␈αthat␈αslides␈αhis␈α240␈αbits␈αalong␈αthe␈αcryptogram␈αa␈αcharacter
␈↓ ↓H
␈↓ ↓Hat␈α∞a␈α∞time␈α∞and␈α∞does␈α∞an␈α
exclusive␈α
or␈α
in␈α
order␈α
to␈α
guess␈α
three␈α
successive␈α
␈↓↓x␈↓∧i␈↓'s␈α
totaling␈α
180␈α
bits--say␈α
␈↓↓x␈↓∧m␈↓↓,
␈↓ ↓H
␈↓ ↓Hx␈↓∧m+1␈↓,␈αand␈α␈↓↓x␈↓∧m+2␈↓.␈αFor␈αeach␈αsuch␈αguess,␈αthe␈αprogram␈αsolves␈αthe␈αlinear␈αequations␈α␈↓↓x␈↓∧m+1␈↓↓␈α=␈αax␈↓∧m␈α␈↓↓+␈αc␈↓␈αto␈αget␈αa
␈↓ ↓H
␈↓ ↓Hconjectured␈α␈↓↓a␈↓␈αand␈α␈↓↓c␈↓.␈α
The␈α
conjectured␈α
␈↓↓a␈↓␈α
and␈α
␈↓↓c␈↓␈α
are␈α
used␈α
to␈α
continue␈α
the␈α
sequence␈α
of␈α
␈↓↓x␈↓∧i␈↓'s,␈α
i.e.␈α
to␈α
get␈α
␈↓↓x␈↓∧m+1␈↓
␈↓ ↓H
␈↓ ↓Hand␈α␈↓↓x␈↓∧m+4␈↓.␈αThese␈αare␈α␈↓↓exclusive-or␈↓ed␈αwith␈αmore␈αof␈α
the␈α
cryptogram␈α
to␈α
get␈α
further␈α
conjectured␈α
plain␈α
text.
␈↓ ↓H
␈↓ ↓HThe␈α∂conjectured␈α∂plain␈α∂text␈α∂is␈α∂tested␈α∂with␈α∂trigram␈α∂tables␈α∂to␈α∂see␈α∂if␈α∞it␈α∞is␈α∞plausible␈α∞English␈α∞and␈α∞any
␈↓ ↓H
␈↓ ↓Hsequences␈αpassing␈αthe␈αtest␈αare␈αdisplayed␈αto␈αthe␈α
villain␈α
at␈α
his␈α
console.␈α
When␈α
he␈α
likes␈α
what␈α
he␈α
sees,␈α
the
␈↓ ↓H
␈↓ ↓Hsearch␈α∞stops␈α∞and␈α∞prints␈α∞the␈α
rest␈α
of␈α
the␈α
message.␈α
This␈α
is␈α
the␈α
probable␈α
word␈α
method␈α
well␈α
known␈α
in
␈↓ ↓H
␈↓ ↓Hcryptography.
␈↓ ↓H

␈↓ ↓H
␈↓ α_The␈αweakness␈αof␈αthe␈αcipher␈αas␈αdescribed␈αby␈αFriedman␈αand␈αHoffman␈αis␈αthat␈αthe␈αkey␈αsequence
␈↓ ↓H
␈↓ ↓His␈αcontinuable␈αonce␈α180␈α
bits␈α
of␈α
it␈α
have␈α
been␈α
guessed.␈α
The␈α
method␈α
can␈α
be␈α
improved␈α
by␈α
subjecting␈α
the
␈↓ ↓H
␈↓ ↓Hrandom␈αoutput␈αof␈αthe␈αnumber␈αgenerator␈αto␈αan␈αinformation␈αlosing␈αtransformation␈αin␈αorder␈αto␈αget␈αthe
␈↓ ↓H
␈↓ ↓Hrunning␈α
key.␈α
Even␈α
using␈α
only␈α
every␈αother␈αbit␈αproduced␈αby␈αthe␈αgenerator␈αwould␈αmake␈αit␈αunobvious
␈↓ ↓H
␈↓ ↓Hhow␈αto␈αproceed,␈αbut␈αsince␈αthe␈αvillain's␈αproblem␈αwould␈αstill␈αbe␈αlinear,␈αmathematics␈αmight␈αsave␈α
him.␈α
A
␈↓ ↓H
␈↓ ↓Hbetter␈αidea␈αwould␈αbe␈αto␈αuse␈αa␈αsecond␈αrandom␈αnumber␈αgenerator␈αto␈αselect␈αwhich␈αbits␈αfrom␈αthe␈αoutput
␈↓ ↓H
␈↓ ↓Hof␈α
the␈α
first␈α
generator␈α
would␈α
go␈α
into␈α
the␈α
key.␈α
While␈α
this␈α
looks␈α
good␈α
to␈α
me,␈α
I␈α
don't␈α
certify␈α
it.
␈↓ ↓H

␈↓ ↓H
␈↓ α_All␈αthis␈αsuggests␈αthe␈αfollowing␈αstrong␈αadequacy␈αcriterion␈αfor␈αan␈αencipherment␈αsystem.␈αSuppose
␈↓ ↓H
␈↓ ↓Hall␈α∞of␈α∞the␈α∞plain␈α∞text␈α∞known␈α∞except␈α∞for␈α
one␈α
character.␈α
Then␈α
it␈α
should␈α
still␈α
require␈α
an␈α
unacceptable
␈↓ ↓H
␈↓ ↓Hamount␈α∀of␈α∪work␈α∪to␈α∪learn␈α∪more␈α∪about␈α∪the␈α∪missing␈α∪character␈α∪than␈α∪is␈α∪suggested␈α∪by␈α∪the␈α∪known
␈↓ ↓H
␈↓ ↓Hremainder␈α⊂of␈α⊂the␈α⊂message.␈α⊂In␈α⊂fact,␈α⊂let␈α⊂me␈α⊂suggest␈α⊂calling␈α⊂such␈α⊂an␈α⊂encipherment␈α⊂system␈α⊂␈↓βstrongly
␈↓ ↓H
␈↓ ↓Hadequate␈↓.
␈↓ ↓H

␈↓ ↓H
␈↓ α_Several␈αyears␈αago␈αan␈αencipherment␈αsystem␈αthat␈αwe␈αhoped␈αwas␈αstrongly␈αadequate␈αwas␈αinstalled
␈↓ ↓H
␈↓ ↓Has␈α∂a␈α∂utility␈α∂program␈α∂at␈α∂the␈α∂Stanford␈α∂Artificial␈α∂Intelligence␈α∂Laboratory␈α∞on␈α∞our␈α∞PDP-10.␈α∞Its␈α∞fate␈α∞is
␈↓ ↓H
␈↓ ↓Hinstructive.␈α
A␈α
villain␈α
replaced␈α
the␈α
source␈α
program␈α
by␈α
one␈α
that␈α
whenever␈α
used␈α
copied␈α
the␈α
name␈α
of␈α
the
␈↓ ↓H
␈↓ ↓Henciphered␈αfile␈αand␈αthe␈αstarting␈αkeyword␈αinto␈αa␈αfile␈αin␈αthe␈αsystem␈αarea.␈αThis␈αhas␈αsubsequently␈αbeen
␈↓ ↓H
␈↓ ↓Hmade␈α
more␈α
difficult,␈α
but␈α
perfect␈α
security␈α
has␈α
not␈α
been␈α
achieved.
␈↓ ↓H

␈↓ ↓H

␈↓ ↓H
   ␈↓ α_␈↓ αh␈↓ β8␈↓ ∧λ␈↓ ∧X␈↓ ¬(␈↓ ¬xSincerely yours,
␈↓ ↓H

␈↓ ↓H

␈↓ ↓H

␈↓ ↓H
␈↓ α_␈↓ αh␈↓ β8␈↓ ∧λ␈↓ ∧X␈↓ ¬(␈↓ ¬xJohn McCarthy
␈↓ ↓H
␈↓ α_␈↓ αh␈↓ β8␈↓ ∧λ␈↓ ∧X␈↓ ¬(␈↓ ¬xDirector, Artificial Intelligence Laboratory
␈↓ ↓H
␈↓ α_␈↓ αh␈↓ β8␈↓ ∧λ␈↓ ∧X␈↓ ¬(␈↓ ¬xProfessor of Computer Science
␈↓ ↓H